Real-time performance is essential for time-critical responses required in high-performance embedded applications such as telecommunications switching equipment, medical monitoring equipment, space navigation and guidance applications, and the like. Such applications must deliver responses within specified time parameters in real-time.
Real-time performance is provided by operating systems that use thread-scheduling mechanisms to schedule threads for execution on a thread priority basis. (A thread is basically a path of execution through a computer program application). For example, the Microsoft WINDOWS CE® operating system provides two-hundred-fifty-six (256) thread priority levels, wherein threads of higher priority are executed before threads of lower priority are executed. Threads of equal priority are executed in a first-in-first-out round-robin fashion. For example, thread A runs, then thread B runs, followed by thread C, and back to thread A.
Thread scheduling mechanisms typically store threads in a “run queue” for subsequent execution. FIG. 1 illustrates a traditional run queue 100 that is implemented as a linked list. The threads 102 in the run queue are sorted based on respective thread priorities. For example, Threads 102-A1 through 102-AJ have respective thread priorities of zero (0), threads 102-B1 through 102-BK have respective thread priorities of one (1), and the like. There can be any number of threads 102 in the run queue.
A thread that is currently executing may be preempted by another thread, or the thread itself may “yield” its access to the processor. Both of these terms refer to the thread being placed into a “non-executing” state. For example, an operating system may put a thread to sleep, or preempt the thread to allow a different thread with a higher priority to execute. In another example, the thread itself may “yield” its access to the processor to wait for the occurrence of a particular event such as the elapse of a predetermined amount of time, or the like, before continuing execution.
Regardless of whether a thread is preempted by another program or whether the thread itself yields its access to the processor, the system's thread scheduling mechanism typically stores the preempted, or yielding thread into a run queue or sleep queue. (More particularly, a reference to the thread is generally stored in the run queue or sleep queue). (Although the thread scheduling mechanism may or may not be part of the operating system, the terms thread scheduling mechanism, operating system, and the like, are often used interchangeably in this description to describe a system's thread scheduling aspects). When a thread's specified sleep time has expired, the scheduling mechanism “wakes-up” the thread by removing the thread from the sleep queue and inserting the thread into the run queue for subsequent execution.
FIG. 2 illustrates a traditional single-dimension sleep queue 200 that is implemented as a linked list. (A traditional sleep queue may also be implemented as a “heap” data structure). For purposes of this description, a sleep queue 200 is any queue for storing any number of threads that are sorted based on time. In this example, the threads 202 in the sleep queue are sorted in a single dimension based on thread wake-up time and thread priority within a particular wake-up time. For example, thread 202-1 has a wake-up time of five (5) milliseconds (ms) and threads 202-2 and 202-3 have respective wake-up times of ten (10) milliseconds. Threads that have the same sleep time are sorted based on priority in a round robin fashion. For example, thread 202-2 has a wake-up time of 10 ms with a thread priority of 0 (in this example, the highest thread priority), and thread 202- . . . has a wake-up time of 10 ms with a thread priority of 5 (a lower priority than a thread priority of 0). In this manner, the threads in the traditional sleep queue are sorted with respect to one-another in a single dimension.
As discussed above, a thread may be preempted by another thread for any number of reasons. One significant reason that a thread may be preempted is so that the operating system, or thread scheduling mechanism can determine if there are any threads of higher priority that need to be executed. Part of this determination, and another significant reason in and of itself, is the operating system may scan the threads stored/referenced in the sleep queue to determine if any need to be woken-up for execution (e.g., inserted into the run queue). Real-time operating systems typically preempt all other threads from executing at predetermined periodic time intervals to perform such thread management.
Thread scheduling mechanisms typically use a hardware timer to produce a system tick to determine a maximum amount of time, or “quantum” that a thread can execute in the system without being preempted. A system tick is a rate at which a hardware timer interrupt is generated and serviced by an operating system. When the timer fires, the thread scheduling mechanism will schedule a new thread for execution if one is ready.
Significantly, an operating system requires exclusive access to a processor during certain thread scheduling procedures such as during sleep queue thread removal procedures and during run queue thread insertion procedures. The operating system uses its system-exclusive access: (a) to remove threads from the sleep queue at or as close as possible to each respective thread's specified wake-up time for subsequent insertion into the run queue; and, (b) to insert each thread removed from the sleep queue into the run queue for execution.
The number of threads to be woken-up at any one time could be any number of threads such as one thread, two threads, or one hundred threads. The more threads that need to be removed from the sleep queue for insertion into the run queue, the greater the amount time is that an operating system requires system-exclusive access to the processor. This system-exclusive access is directly controlled by the operating system and cannot typically be preempted by any other thread.
The non-deterministic and non-preemptable nature of traditional sleep queue thread removal and run queue thread insertion procedures creates a number of significant problems. One problem, for example, is that an operating system cannot typically be guaranteed to schedule other threads within predetermined time parameters because of such non-deterministic thread management techniques. This means that a preempted thread (a thread that was executed but that was blocked during sleep queue thread removal) won't execute again for an unknown amount of time. The respective wake-up times of one or all of the threads that that need to be removed from a sleep queue at any one moment in time may have already long passed before they are removed and inserted into the run queue. Analogously, by the time a thread that is inserted into the run queue gets executed, the thread's purpose or the event that the thread is responding to may have passed long ago.
Accordingly, traditional sleep queue thread removal and run queue thread insertion procedures do not typically allow an operating system to schedule other threads for execution within deterministic/predetermined time parameters.